package fun.coding.array;

import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.Set;
import java.util.Stack;

import org.apache.commons.lang3.ArrayUtils;
import org.apache.commons.lang3.tuple.Pair;

import fun.coding.search.BinarySearch;
import fun.coding.search.BinarySearchImpl;

public class ArrayManipulationImpl implements ArrayManipulation {

    public enum MethodType{
        SORT,
        HASH
    }
    
    /* For example, [3, 0, 1, 0, 0, 9, 0, 7] => remove 0 and condense [3, 1, 9, 7]
     * NOTE: look below for a better method. 
     */
    @Override
    public void removeDuplicateAndCondenseArray(int[] array, int k) {
        int j = 0;
        for(int i = 0; i < array.length; ++i) {
            if(array[i] == k) {
              while(j <= i) {
                  if(array[j] == k) {
                      break;
                  }
                  j++;
              }
            } else {
                if(j < i && (array[j] == k)) {
                    array[j] = array[i];
                    array[i] = k;
                    j++;
                }
            }

        }
        
        System.out.println("new arrays is: ");
        for(int i = 0; i < j; ++i) {
            System.out.println(array[i]);
        }
    }

    /* The same problem as above, with 2 pointers, keep copying unless find k
     *  [3, 0, 1, 0, 0, 9, 0, 7] => remove 0 and condense [3, 1, 9, 7]
     *  [0, 3, 0, 1, 0, 0, 9, 0, 7]
     * */
    @Override
    public void removeDuplicateAndCondenseArrayBetter(int[] array, int k) {
        if(array == null || array.length == 0)
            return;
        
        int i = 0, j = 0;
        
        while(i < array.length) {
            if(array[i] == k) {
                i++;
            } else {
                array[j] = array[i];
                i++;
                j++;
            }            
        }
        
        System.out.println("new arrays is: ");
        for(int t = 0; t < j; ++t) {
            System.out.println(array[t]);
        }
        
    }
    
    /* for example, 3, 4, 4, 4, 2, 2, 3, 4 will return 3 [4, 4, 4]
     */
    @Override
    public int maxSameSubSequence(int[] array) {
        if(array.length == 0) {
            return 0;
        }
        
        int currentSameValue = array[0];
        int maxSameLength = 1;
        
        int currentLength = 1;
        for(int i = 1; i < array.length; i++) {
            if(array[i] == currentSameValue) {
                currentLength++;
            } else {
                currentSameValue = array[i];
                currentLength = 1;
            }
            
            if(currentLength > maxSameLength) {
                maxSameLength = currentLength;
            }
        }
        
        return maxSameLength;
        
    }

    /**
     * let's say the window size k is 3
     * Let's assume there is no duplicate
     * given an array [7, 6, 9, 8, 2, 3, 4] will print out {9, 9, 9, 8, 4}
     */
    @Override
    public void printMaxSlidingWindow(int[] array, int k) {
        // Here I will use a maxHeap to maintain the max value, howver, this will make the time complexity O(N*K)
        
        // Java priority queue default would be a min heap, so that's why I need a comparator to make it a max heap 
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(k, new MaxHeapComparator());
        
        for(int i = 0; i < array.length; i++) {
            if(i < k) {
                pq.add(array[i]);
                continue;
            }
            
            System.out.println(pq.peek());
            
            pq.remove(array[i - k]);
            pq.add(array[i]);
            
        }
        
        System.out.println(pq.peek());
    }
    
    private class MaxHeapComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
        
    }

    /* Returns kth largest element in an array
     * {2, 9, 3, 7, 8} 3rd largest would return 7.
     * 
     * However, using selection algorithm (kinda like quick sort O(NlgN) ), it is O(N), since
     * we are dumping the other half 
     * 
     * My below implemention is dump, if use heap, just need a min head of size k. 
     */
    @Override
    public int largestKthElementHeapSolution(int[] array, int k) {
        
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(array.length, new MaxHeapComparator());
        
        for(int i = 0; i < array.length; i++) {
            pq.add(array[i]);
        }
        
        int kthLargest = -1;
        while(k > 0) {
            if(!pq.isEmpty()) {
                kthLargest = pq.poll();
            }
            k--;
        }
        
        if(k == 0) {
            System.out.println(String.format("%d th largest element is ", kthLargest));
            return kthLargest;
        } else {
            System.err.println("Wrong...");
            return -1;
        }
        
    }

    /*
     * Return a unique non-descending triplet that sums up to 0. 
     * The idea is to have 2 pointers at both end. O(N^2) vs naive O(N^3). Could be reduced to a + b = c
     * S = {-1 0 1 2 -1 -4},
     *  (-1, 0, 1)
     *  (-1, -1, 2) 
     */
	@Override
	public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
		// java default sort is ascending order.
		Arrays.sort(num);
		//Need to avoid duplicate, that's why use heap.
		Set<ArrayList<Integer>> triplet = new HashSet<ArrayList<Integer>>();
		
		for(int i = 0; i < num.length; i++) {
			int j = i + 1;
			int k = num.length - 1;
			
			int sumTarget = 0 - num[i];
			
			while(j < k) {
				if(num[k] > sumTarget - num[j]) {
					k--; // end move left
				} else if(num[k] < sumTarget - num[j]) {
					j++; // begin move right
				} else {
					// find a triplet
					ArrayList<Integer> l = new ArrayList<Integer>();
					l.add(num[i]);
					l.add(num[j]);
					l.add(num[k]);
					triplet.add(l);
					j++;
					k--;
				}
				
			}
		}
			
		return  new ArrayList<ArrayList<Integer>>(triplet);
	}

	/*
	 * Let's assume a and b are already sorted, and merge these two arrays.
	 * a {3, 5, 7, 9}
	 * b {2, 4, 7, 9, 11, 13}
	 * => {2, 3, 4, 5, 7, 7, 9, 9, 11, 13}
	 */
	@Override
	public ArrayList<Integer> mergeTwoSortedArrays(int[] a, int[] b) {
		ArrayList<Integer> result = new ArrayList<Integer>();
		
		int i = 0;
		int j = 0;
		
		while(i < a.length && j < b.length) {
			if(a[i] < b[j]) {
				result.add(a[i]);
				i++;
			} else if(a[i] > b[j]) {
				result.add(b[j]);
				j++;
			} else {
				result.add(a[i]);
				result.add(b[j]);
				i++;
				j++;
			}
		}
		
		while(i < a.length) {
			result.add(a[i]);
			i++;
		}
		
		while(j < b.length) {
			result.add(b[j]);
			j++;
		}
		
		return result;
	}

	/*
	 * Reverse an interger, 123 => 321 
	 * -123 => -321
	 * could be an over flow case.
	 */
    @Override
    public int reverse(int x) {
        int sign = (x > 0) ? 1 : -1;
        
        if(sign == -1) {
            x = x * -1;
        }
        
        int ret = 0;
        
        while (x > 0) {
            int digit = x % 10;
            ret = ret * 10 + digit;
            x = x / 10;
        }
        
        if(ret > Integer.MAX_VALUE)
            ret = Integer.MAX_VALUE;
        
        if(ret < Integer.MIN_VALUE)
            ret = Integer.MIN_VALUE;
        
        return ret * sign;
    }

    /* For example, {5, 5, 3, 2, 3} would return 2
     * The trick is using xor, 0^x = x, x^x = 0
     * 
     * If the array does not have this property, will probably use some extra storage.
     * 
     * An extension would be find the only two numbers appear only once in a paired array. 
     * http://zhedahht.blog.163.com/blog/static/2541117420071128950682/
     * 
     */
	@Override
	public int findNumOnlyAppearOnceInPairArray(int[] array) {
		int exclusiveOrRes = 0;
		
		for(int i = 0; i < array.length; ++i) {
			exclusiveOrRes ^= array[i];
		}
		
		return exclusiveOrRes;
	}

	// TODO: FIXME, it is buggy!
	/* 
	 * Use selection sort without sorting this array to get the median in O(N)
	 * For example, {5, 3, 2, 4, 6} would return 4. 
	 * {5, 3, 2, 4, 6, 1} would return 3 (return the first one if it is even.)
	 * http://discuss.codechef.com/questions/1489/find-median-in-an-unsorted-array-without-sorting-it
	 * */
	@Override
	public int findMedian(int[] array) {
		if(array.length == 0)
			return -1;
		
		if(array.length == 1)
			return array[0];
		
		int left = 0;
		int right = array.length - 1;
		
		while(true) {
			int pivotIndex = partition(array, left, right);
			// FIXME: this should be length/2 -1 for even number
			if(pivotIndex == array.length / 2) {
				return array[pivotIndex];
			} else if(pivotIndex > array.length / 2) {
				right = pivotIndex - 1;
			} else {
				left = pivotIndex + 1;
			}
		}
		
	}

	@Override
	public int findMedianStream(InputStream is) {
	    // TODO Auto-generated method stub
	    return 0;
	}
	
	/* Just to compare those numbers with each other. There should be only at most 3 comparisons needed. 
	 * */
	@Override
	public int find3Median(int a, int b, int c) {
		if(a > b) {
			if(b > c)
				return b;
			else {
				if(a > c)
					return c;
				else
					return a;
			}
			
		} else {
			if(b < c)
				return b;
			else {
				if(a > c)
					return c;
				else
					return a;
				
			}
		}
		
	}
	
	private int partition(int[] array, int left, int right) {
		int pivotIndex = left + (right - left) / 2;
		int pivot = array[pivotIndex];
		
		swap(array, right, pivotIndex);
		
		int i = left;
		int j = right - 1;
		
		while(i <= j) {
			while(array[i] <= pivot) {
				i++;
			}
			
			while(array[j] >= pivot) {
				j--;
			}
			
			if(i <= j) {
				swap(array, i, j);
				i++;
				j--;
			}
		}
		// FIXME: should swap(array, i, right);
		swap(array, i, j);
		return i;
	}
	
	private void swap(int[] array, int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
	
	/*
	 *  a1 = {2, 3, 5}
	 *  a2 = {1, 8}
	 *  a3 = {4, 6, 7}
	 *  
	 *  Use a combination of hashmap and heap to track which array has the minimal value.
	 *  will return 1, 2, 3, 4, 5, 6, 7, 8
	 * */
    @Override
    public ArrayList<Integer> mergeNSortedArray(ArrayList<ArrayList<Integer>> al) {
       
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
        HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
        
        int i = 0;
        while(heap.size() < al.size()) {
            heap.add(al.get(i).get(0));
            hm.put(al.get(i).get(0), i);
            i++;
        }
        
        ArrayList<Integer> result = new ArrayList<Integer>();
        
        while(!heap.isEmpty()) {
            int min = heap.poll();
            System.out.println("min is " + min);
            
            result.add(min);
            int index = hm.get(min);
            System.out.println("index is " + index);
            
            // TODO: instead of getting the index, i guess I could delete the element from the 
            // arraylist and always get the first one
            int oldIndex = al.get(index).indexOf(min);
            System.out.println("oldIndex is " + oldIndex);
            
            if(oldIndex + 1 < al.get(index).size()) {
                int num = al.get(index).get(oldIndex + 1);
                heap.add(num);
                hm.put(num, index);
            }
        }
        
        return result;
    }

    /**
     * Let's assume there is no duplicate elements in a1, a2
     * a1 = {5, 9, 11, 13, 17}
     * a2 = {2, 6, 18, 21}
     * k = 1 -> 2
     * k = 2 -> 5
     * This algorithm is O(k), there exits a lgM + lgN using binary search. 
     * http://leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html
     */
    @Override
    public int findKthSmallestInTwoSortedArray(int[] a1, int[] a2, int k) {
        
        if(a1 == null || a2 == null || k < 0 || k > (a1.length + a2.length)) {
            return -1;
        }
        int i = 0, j = 0;
        
        for(int t = 0; t < k - 1; ++t) {
            if(a1[i] < a2[j]) {
                i++;
            } else {
                j++;
            }
        }
        
        return a1[i] < a2[j] ? a1[i] : a2[j]; 
    }

    /**
     * There are definitely duplicates in these two arrays, 
     * a1 = {5, 9, 11, 13, 17}
     * a2 = {2, 5, 11, 17, 21, 29}
     * {5, 11, 17}, 
     * a follow up would be what happens if one of the arrays is huge, then we could perform binary search on the huge one, 
     * resulting NlgM where M is huge, thus better than O(M+N).
     */
    @Override
    public ArrayList<Integer> intersectTwoSortedArrays(int[] a1, int[] a2) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        int i = 0, j = 0;
        
        while(i < a1.length && j < a2.length) {
            if(a1[i] < a2[j]) {
                i++;
            } else if(a1[i] > a2[j]) {
                j++;
            } else {
                res.add(a1[i]);
                i++;
                j++;
            }
        }
        
        return res;
    }

    /**
     * given a unsorted array, find all unique pairs that sums to a number, could be duplicate
     * a = {5, 2, 5, 2, 8, 7, 3, 11};
     * There are two ways, one without extra space by sorting it, O(NlgN)
     * The other is use HashMap<int, numberOccurence>, O(N)
     */
    @Override
    public ArrayList<ArrayList<Integer>> twoSum(int[] a, int sum, MethodType t) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        
        if(t == MethodType.SORT) {
            Arrays.sort(a);
            
            int i = 0;
            int j = a.length - 1;
            
            while(i <= j) {
                if(a[i] + a[j] < sum) {
                    i++;
                } else if(a[i] + a[j] > sum) {
                    j--;
                } else {
                    // FIXME: this has bug, can't remove duplicate for 2, 2, 5, 5
                    ArrayList<Integer> al = new ArrayList<Integer>();
                    al.add(a[i]);
                    al.add(a[j]);
                    res.add(al);
                    i++;
                    j--;
                }
            }
        }else if(t == MethodType.HASH) {
            // define something like this is fine, but maybe in method signature, use Map interface.
            HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
            for(int i : a) {
                hashMap.put(i, hashMap.containsKey(i) ? hashMap.get(i) + 1 : 1);
            }
            
            for(int i: a) {
                if(hashMap.containsKey(i) && hashMap.containsKey(sum - i)) {
                    ArrayList<Integer> al = new ArrayList<Integer>();
                    al.add(i);
                    al.add(sum-i);
                    res.add(al);
                    // FIXME: here, the same thing, can't remove duplicate
                    
                    // Could make this a function.
                    if(hashMap.get(i) == 1) {
                        hashMap.remove(i);
                    } else {
                        hashMap.put(i, hashMap.get(i) - 1);
                    }
                    
                    if(hashMap.get(sum - i) == 1) {
                        hashMap.remove(sum - i);
                    } else {
                        hashMap.put(sum - i, hashMap.get(sum - i) - 1);
                    }
                }
            }
            
        }
        
        return res;
    }

    /** sorted array return k element that is nearest to it
     * a = {2, 4, 5, 7, 9, 13} num = 5, k = 2 -> {4,7}; num = 5,  k = 3, -> {2, 4, 7}
     * num = 2, k = 2 -> {4, 5}
     * The method I used here is just a simple simulation, but need to check the array out of bound situation.
     * An alternative is to start from i = 0, j = length -1, find length - 1 - k , same thing.
     * 
     */
    @Override
    public ArrayList<Integer> findKNearestNumber(int[] a, int k, int num) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        BinarySearch bs = new BinarySearchImpl();
        int index = bs.binarySearch(a, num, 0, a.length - 1);
        
        System.out.println("num index is " + index);
        
        if(index == -1)
            return res;
        
        int i = index - 1;
        int j = index + 1;
        
        for(int it = 0; it < k; ++it) {
            if(i < 0) {
                res.add(a[j]);
                j++;
            }
            
            if(j >= a.length) {
                res.add(a[i]);
                i--;
            }
            
            if(i >= 0 & j < a.length) {
                // Or use a if else, only decrease one index at a time.
                res.add(Math.abs(a[i] - num) > Math.abs(a[j] - num) ? a[j++] : a[i--]);
            }
        }
        
        return res;
    }

    /* In short, reservoir sampling is used for unknown size of stream, the catch is we decide whether putting the current value based on the current probabililty.
     * http://en.wikipedia.org/wiki/Reservoir_sampling
     * */
	@Override
	public int[] reservoirSampling(int size, int k) {
		int[] a = new int[size];
		
		for(int i = 0;i < size; ++i) {
			a[i] = i;
		}
		
		int[] result = new int[k];
		
		for(int i = 0; i < k; ++i) {
			result[i] = a[i];
		}
		
		Random r = new Random(System.currentTimeMillis());
		for(int i = k; i < size; ++i) {
			int j = r.nextInt(i);
		//	System.out.println("j is " + j + "i is " + i);
			if(j < k) {
				result[j] = a[i];
			}
		}
		
		return result;
	}

	/*
	 * 
	[5, 7, 6, 4, 9, 10, 2, 1] => 
	[1, 2, 4, 5, 6, 7, 9, 10]
	
	[1-2]
	[4-7]
	[9-10]
	
	[1, 2, 4, 1]
	[1-2]
	[4]
	
	I will just simply sort it and count it.
	 * */
	@Override
	public void printIntervalsArray(int[] array) {
		Arrays.sort(array);
		
		if(array.length == 0)
			return;
		
		if(array.length == 1)
			System.out.println(array[0]);
		
		int start = array[0];
		int end = array[0];
		
		for(int i = 1; i < array.length; ++i) {
			if(!(array[i] - array[i - 1] == 1 || array[i] == array[i - 1])) {
				System.out.println(start + "-" + end);
				start = array[i];	
			}
			end = array[i];
		}
		
		if(start != end)
			System.out.println(start + "-" + end);
		else 
			System.out.println(start);
		
	}

	/* This is my facebook onsite question, I didn't see any tricks. Just plain implementation.
	 * Made a stupid mistake then using two separate for loops instead of a nested 2 for loop. 
	 * 
	 * 3, 4, 5, 2
	 * 7, 2, 1, 9
	 * 4, 9, 6, 5
	 * 
	 * */
    @Override
    public int[] copyArray(int[] a, int dx, int dy, int sx, int sy, int w, int h, int arrayWidth, int arrayHeight) {
        // assume valid
        
        int[][] source = new int[h][w];
        
        for(int i = 0; i < h; ++i) {
            for(int j = 0; j < w; ++j)
                source[i][j] = a[(dx + i) * arrayWidth + dy + j];
        }
        
        for(int i = 0; i < h; ++i) {
            for(int j = 0; j < w; ++j) {
                a[(sx + i) * arrayWidth + sy + j] = source[i][j];
            }
        }
        
        return a;
        
    }

    /* print the spiral like peeling off the apple skin. 
     * 1, 2, 3,
     * 8, 9, 4, 
     * 7, 6, 5
     *  would print out 1, 2, 3, 4, 5, 6, 7, 8, 9
     * 
     * 1 2 3 4
     * 5 6 7 8
     * 9 8 7 6
     * 5 3 2 2
     * */
    @Override
    public void printSpiralMatrix(int[][] array) {
        int col = array[0].length;
        int row = array.length;
        
        System.out.println("row and col are " + row + ", " + col);
        int k = 0;
        
        do {
            printSpiralHelper(array, row, col, k);
            row -= 2;
            col -= 2;
            k++;
        } while(row >= 1 && col >= 1); 
    }

    /*
     * 
     * http://leetcode.com/2010/05/printing-matrix-in-spiral-order.html*/
    private void printSpiralHelper(int[][] array, int row, int col, int k) {
        int i;
        int j;
        
        // The only trick is to handle the 1 row/col case separately. 
        if(row == 1) {
            for(i = k; i < col; ++i)
            System.out.print(array[k][i] + " ");
            return;
        }
        
        if(col == 1) {
            for(i = k; i < row; ++i)
            System.out.print(array[i][k] + " ");
            return;
        }
        
        for(i = k, j = k; j < col; ++j) {
            System.out.print(array[i][j] + " ");
        }
        
        for(i = k + 1, j = k + col - 1; i < row; ++i) {
            System.out.print(array[i][j] + " ");
        }
        
        for(i = k + row - 1, j = k + col - 2; j >= k; --j) {
            System.out.print(array[i][j] + " ");
        }
        
        for(i = k + row - 2, j = k; i >= k + 1; --i) {
            System.out.print(array[i][j] + " ");
        }
        
    }

    /* http://www.glassdoor.com/Interview/Was-asked-how-I-would-implement-division-without-using-division-or-mod-operators-The-answer-should-return-in-the-form-quot-QTN_138161.htm
     * Normally we only think about using subtraction, but it will be very slow. Using left shift is much faster.
     * m / n,   e.g., 5/2 = 2, 6/2 = 3
     * This will be efficient than the original method. To the order of O(lgN), and shift is faster than minus.
     * Let's assume they are both positive integers.  
     * */
    @Override
    public Pair<Integer, Integer> divideWithoutSubtraction(int m, int n) {
        if (n == 0) {
            return Pair.of(0, 0);
        }
        // assume all positive
        m = Math.abs(m);
        n = Math.abs(n);
        
        int quote = 0;
        while (m >= n) {
            int shiftCount = 0;
            int t = n;
            while ((t << 1) < m) {
                shiftCount++;
                t = t << 1;
            }
            
            quote += Math.pow(2, shiftCount);
            m -= (int)Math.pow(2, shiftCount) * n;
        }
        return Pair.of(quote, m);
    }

    @Override
    public Pair<Integer, Integer> divideWithSubtraction(int m, int n) {
        if (n == 0) 
            return Pair.of(0, 0);
        
        int d = 0;
        // could be positive or negative
        int t = m * n;
        if (t > 0) {
            if (m > 0) {
                while (m >= n) {
                    m -= n;
                    d++;
                }
            } else {
                while (m <= n) {
                    m -= n;
                    d++;
                }
            }
            t = 1;
        } else if (t < 0) {
            if (m > 0) {
                while (m >= Math.abs(n)) {
                    m += n;
                    d++;
                }
            } else {
                while (Math.abs(m) >= n) {
                    m += n;
                    d++;
                }
            }
            t = -1;
        } else {
            return Pair.of(0, 0);
        }
        
        return Pair.of(d * t, m);
    }
    
    /*
     * http://discuss.leetcode.com/questions/259/largest-rectangle-in-histogram
     * http://tianrunhe.wordpress.com/2012/07/26/largest-rectangle-in-histogram/
     * Even using a stack to maintain the non-decreasing order, it is worst case O(N^2) and avg O(N).
     */
	@Override
	public int largestRectangleArea(int[] height) {
	    if (height == null || height.length == 0) {
            return 0;
        }
	    
	    int max = 0, n = height.length;
	    Stack<Integer> s = new Stack<Integer>();
	    
	    for (int i = 0; i < n; ++i) {
	        if (s.isEmpty()) {
	            s.add(height[i]);
	            continue;
	        }
	        
	        int prev = s.peek();
	        if (height[i] >= prev) {
	            s.add(height[i]);
	        } else {
	            // need to pop the stack if encounters a smaller value
	            int step = 1;
	            // only pop up enough that i can maintain a non-decreasing stack. 
	            while (!s.isEmpty() && s.peek() > height[i]) {
	                max = Math.max(max, s.pop() * step);
	                step++;
	            }
	            
	            // have to add the element back with the current smallest value. 
	            for (int j = 0; j < step; ++j) {
	                s.add(height[i]);
	            }
	        }
	    }
	    
	    // has to make sure the stack is empty. 
        int step = 1;
        while (!s.isEmpty()) {
            max = Math.max(max, s.pop() * step);
            step++;
        }

		return max;
	}
	
	/* This is the naive O(N^2) implementation, starting from one point and expand on two sides.  
	 * */
	@Override
	public int largestRectangleAreaONSquare(int[] height) {
	    if (ArrayUtils.isEmpty(height)) {
	        return 0;
	    }
	    
	    int n = height.length;
	    int max = 0;
	    for (int i = 0; i < n; ++i) {
	        int s = 1;
	        int j = i - 1;
	        
	        while (j >= 0 && height[j] >= height[i]) {
	            s++;
	            j--;
	        }
	        
	        j = i + 1;
	        while(j < n && height[j] >= height[i]) {
	            s++;
	            j++;
	        }
	        int m = s * height[i];
	        max = Math.max(m, max);
	    }
	    
	    return max;
	}
	
	/* Microsoft onsite STB questions, {1, 2, 3, 4, 5} k = 3 => {3, 4, 5, 1, 2} 
	 * {1, 2, 3, 4, 5, 6} k = 3 => {4, 5, 6, 1, 2, 3}
	 * don't use extra space 
	 * There is a trick part that need to check if the node has been visited or not or else it will end up in an infinite loop.
	 * I make this way more complicated than it should be :(
	 * But this is O(N).
	 * Tony suggested a shifting method, 1,2,3,4,5 => 5,4,3,2,1 => since k = 3, 3,4,5, 1,2
	 * */
	@Override
	public void rotateArrays(int[] array, int k) {
		if(array == null || k < 0 || k > array.length || array.length <= 1)
			return;
		
		int start = 0;
		int n = 0;
		int nextIndex = k % array.length;
		int prev = array[0];
		
		while(n < array.length) {
			System.out.println("nextIndex is " + nextIndex);
			int tmp = array[nextIndex];
			array[nextIndex] = prev;
			prev = tmp;
			
			if(start == nextIndex) {
			    nextIndex++;
			    start = nextIndex;
			    prev = array[nextIndex];
                nextIndex = (nextIndex + k) % array.length;
                
            } else {
                nextIndex = (nextIndex + k) % array.length;
            }
			n++;
		}
		
		System.out.println("rotated array is ");
		for(int i : array) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

	/* {1, 2, 3, 4, 5, 6} k = 3 => {4, 5, 6, 1, 2, 3} 
	 * All I need to do is shift k times. O(kN).
	 * */
	@Override
	public void rotateArraysBetter(int[] array, int k) {
	    for(int i = 0; i < k % array.length; ++i) {
	        int end = array[array.length - 1];
	        // This way it only iterate length - 1 times while j>=0 will do length times. 
	        for(int j = array.length - 1; j > 0; --j) {
	            array[j] = array[j - 1];
	        }
	        array[0] = end;
	    }
	    
	    for(int i : array) {
            System.out.print(i + " ");
        }
        System.out.println();
	}
	
	
	/* {100, 3, 2, 4, 99, 97, 98} return 97, 98, 99, 100
	 * Let's assume there is no duplicate. 
	 * 1) Sort will solve it. 
	 * 2) 
	 * */
	public class Node {
	    int min;
	    int max;
	    
	    int getMin() {
	        return min;
	    }
	    
	    int getMax() {
	        return max;
	    }
	    
	    void setMin(int min) {
	        this.min = min;
	    }
	    
	    void setMax(int max) {
	        this.max = max;
	    }
	    
	}
	
    @Override
    public ArrayList<Integer> findLongestIncreasingSeq(int[] array) {
        HashSet<Node> map = new HashSet<Node>();
        
        
        return null;
    }

    /* Shawn's ASW question
     * For example, 15 = 7 + 8, 4 + 5 + 6
     * print out all of those pairs*/
	@Override
	public ArrayList<Integer> findContinuousSum(int n) {
		
		return null;
	}
	
	/* Basically use bit operation for add*/
	@Override
	public int calculateSumWithoutAdd(int n) {
		// TODO Auto-generated method stub
		return 0;
	}
	
    /* find all the prime numbers that is less n.
     * e.g., 2 -> empty, 3 -> 2, 5 -> 2, 3
     * Microsoft onsite, if isPrime will be called multiple times, it is better to 
     * pre-calculate it and store it. If a number is multiple of a prime, then that number is not a prime. 
     *  
     * */
    @Override
    public ArrayList<Integer> findPrimes(int n) {
        if (n <= 2) return null;
        
        ArrayList<Integer> res = new ArrayList<Integer>();
        res.add(2);
        
        // Microsoft focuses on giving a solution first, then keep optimizing it. 
        for (int i = 3; i < n; i += 1) {
            boolean isPrime = true;
            for (int j : res) {
                if (i % j == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                res.add(i);
            }
        }
        
        return res;
    }		

}
